package double_linked_list_with_vhead;

import java.util.ArrayList;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        doubleLinkedListWithDummyHead list = new doubleLinkedListWithDummyHead();
        list.addFirst(2);
        list.addFirst(1);
        list.addLast(3);
        list.addLast(2);
        list.addLast(2);
        list.addIndex(3, 9);
        System.out.println(list);
        list.removeValueAll(2);
        System.out.println(list);
    }
}

class doubleLinkedListWithDummyHead {
    Node dummyHead;
    Node dummyTail;
    int value;
    int size;

    public doubleLinkedListWithDummyHead() {
        dummyHead = new Node(-1);
        dummyTail = new Node(-1);
    }

    public doubleLinkedListWithDummyHead(Node dummyHead, Node dummyTail) {
        this.dummyHead = dummyHead;
        this.dummyTail = dummyTail;
    }

    private boolean indexIsIllegal(int index, String flag) {
        if (flag.equals("add") || flag.equals("query") || flag.equals("reverse")) {
            if (index < 0 || index > size) {
                System.out.println("index is illegal!");
                return false;
            }
        } else if (flag.equals("delete")) {
            if (index < 0 || index >= size) {
                System.out.println("index is illegal!");
                return false;
            }
        }
        return true;
    }

    public void addIndex(int index, int value) {
        String flag = "add";
        if (indexIsIllegal(index, flag)) {
            if (index == 0) {
                addFirst(value);
            } else if (index == size - 1) {
                addLast(value);
            } else {
                Node node = new Node(value);
                Node tempNode = dummyHead.next;
                for (int i = 0; i < index - 1; i++) {
                    tempNode = tempNode.next;
                }
                tempNode.next.prev = node;
                node.next = tempNode.next;
                tempNode.next = node;
                node.prev = tempNode;
                size ++;
            }
        }
    }

    public void addLast(int value) {
        Node node = new Node(value);
        if (size == 0) {
            dummyHead.next = node;
            node.prev = dummyHead;
        } else {
            node.prev = dummyTail.prev;
            dummyTail.prev.next = node;
        }
        dummyTail.prev = node;
        node.next = dummyTail;
        size++;
    }

    public void addFirst(int value) {
        Node node = new Node(value);
        if (size == 0) {
            dummyTail.prev = node;
            node.next = dummyTail;
        } else {
            node.next = dummyHead.next;
            dummyHead.next.prev = node;
        }
        dummyHead.next = node;
        node.prev = dummyHead;
        size ++;
    }

    public int queryIndex(int index) {
        String flag = "query";
        if (indexIsIllegal(index, flag)) {
            Node tempNode = dummyHead.next;
            for (int i = 0; i < index; i++) {
                tempNode = tempNode.next;
            }
            return tempNode.value;
        }
        return -1;
    }

    public int reverseIndex(int index, int newValue) {
        String flag = "reverse";
        if (indexIsIllegal(index, flag)) {
            Node tempNode = dummyHead.next;
            for (int i = 0; i < index; i++) {
                tempNode = tempNode.next;
            }
            int oldValue = tempNode.value;
            tempNode.value = newValue;
            return oldValue;
        }
        return -1;
    }

    private void unlink(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.next = node.prev = null;
    }

    private Node findNode(int index) {
        Node tempNode = null;
        if (index < (size >> 2)) {
            tempNode = dummyHead.next;
            for (int i = 0; i < index; i++) {
                tempNode = tempNode.next;
            }
        } else {
            tempNode = dummyTail.prev;
            for (int i = size - 1; i > index; i--) {
                tempNode = tempNode.prev;
            }
        }
        return tempNode;
    }

    public void removeIndex(int index) {
        String flag = "delete";
        if (indexIsIllegal(index, flag)) {
            Node node = findNode(index);
            unlink(node);
        }
    }

    public void removeValueOnce(int value) {
        Node tempNode = dummyHead.next;
        while (tempNode.next != null) {
            if (tempNode.value == value) {
                unlink(tempNode);
                return;
            }
            tempNode = tempNode.next;
        }
    }

    public void removeValueAll(int value) {
        Node tempNode = dummyHead.next;
        while (tempNode.next != null) {
            if (tempNode.value == value) {
                Node next = tempNode.next;
                unlink(tempNode);
                tempNode = next;
            } else {
                tempNode = tempNode.next;
            }
        }
    }

    public String toString() {
        Node tempNode = dummyHead.next;
        String ret = "";
        while (tempNode.next != null) {
            ret += tempNode.value + "->";
            tempNode = tempNode.next;
        }
        ret += "NULL";
        return ret;
    }
}

class Node {
    Node prev;
    int value;
    Node next;

    public Node(){}

    public Node(Node prev, int value, Node next) {
        this.prev = prev;
        this.value = value;
    }

    public Node(int value) {
        this.value = value;
    }
}
